#include<utility>
#include<iostream>
template <typename Object>

class List
{
private:
  struct Node
  {
    Object data;
    Node *prev;
    Node *next;

    Node( const Object &d = Object{} , Node *p = nullptr,
	                                Node *n = nullptr)
      : data{ d }, prev{ p }, next{ n } { }

    Node(Object && d, Node *p = nullptr, Node *n = nullptr)
      : data{ std::move(d) }, prev{ p }, next{ n } { }
  };
  /**< 记录节点的位置，并且提供前后节点的信息.*/

public:
  class const_iterator
  {
  public:
    const_iterator() : current{ nullptr }
    {}

    const Object & operator*() const
    { return retrieve(); }
    const_iterator & operator++ ()
    {
      current = current->next; 
      return *this;
    }
    const_iterator operator++ ( int )
    {
      const_iterator old = *this;
      ++( *this );
      return old;
    } //后缀形式的++，说明实现的时候前缀形式运算比后缀形式更快（我自己的笔记，不是注释）
    bool operator== (const const_iterator & rhs ) const
    { return current == rhs.current; }
    bool operator!= (const const_iterator & rhs ) const
    { return !( *this == rhs );}

  protected:
    Node *current ;

    Object & retrieve() const
    { return current->data; }

    const_iterator( Node *p ) : current{ p }
    {}

    friend class List<Object>;
    
  };
  /**<编写了一个要用的编译器的逻辑*/

  class iterator : public const_iterator
  {
  public:
    iterator()
    {}

    Object & operator* ()
    { return const_iterator::retrieve(); }
    const Object & operator* () const
    { return const_iterator::operator*(); }

    iterator & operator++ ()
    {
      this->current = this->current->next;
      return *this;
    }

    iterator operator++(int)
    {
      iterator old = *this;
      ++(*this);
      return old;
    }
    /**<因为更改了返回值的类型所以不得不重新编写前缀和后缀的逻辑*/

  protected:
    iterator( Node *p ) : const_iterator{ p }
    {}

    friend class List<Object>;
  };
  /**< 继承*/

public:
  List()
  {
    init();
  }
  
   List(const List &rhs)
  {
    init();
    for( auto & x : rhs )
      push_back(x);
  } 
  ~List( )
  {
    clear();
    delete head;
    delete tail;
  }
  
  List & operator= ( const List & rhs )
  {
    List copy = rhs;
    std::swap( *this,copy );
    return *this;
  }
  List( List && rhs)
    :theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
  {
    rhs.theSize = 0;
    rhs.head = nullptr;
    rhs.tail = nullptr;
  }
  
  List & operator= ( List && rhs )
  {
    std::swap( theSize, rhs.theSize );
    std::swap( head, rhs.head );
    std::swap( tail, rhs.tail );
    return *this;
  }

 
  iterator begin( )
  { return { head->next }; }
  const_iterator begin() const
  { return {head->next}; }
  iterator end()
  { return {tail}; }
  const_iterator end() const
  { return {tail}; }
  /**< 写了一个迭代器，给const_iterator和iterator分别整了个到头和尾的功能*/

  int size( ) const
  { return theSize; }
  /**< 查看List的长度*/
  bool empty() const
  { return size( ) == 0; }
  /**< 判断列表是否为空*/

  void clear( )
  {
    while( !empty() )
      pop_front();
  }
  /**< 清除Lish中的所有元素*/

  Object & front()
  { return *begin(); }
  Object & front() const
  { return *begin(); }
  Object & back()
  { return *--end();}
  const Object & back() const
  { return *--end(); }
  void push_front( const Object & x )
  { insert( begin(), x ); }
  void push_front( Object && x )
  { insert( begin(),std::move(x) ); }
  void push_back(const Object & x )
  { insert( end(),x ); }
  void push_back(Object && x )
  { insert( end(), std::move( x ) ); }
  void pop_front()
  { erase( begin( ) ); }
  void pop_back()
  { erase ( --end() ); }
  /**< 各种Lish应该拥有的功能的实现*/

  iterator insert( iterator itr, const Object & x )
  {
    Node *p = itr.current;
    theSize++;
    return iterator( p->prev = p->prev->next =new Node(x,p->prev,p ) );
  }
  iterator insert( iterator itr , Object && x)
  {
    Node *p = itr.current;
    theSize++;
    return iterator( p->prev = p->prev->next = new Node(x, p->prev,p) );
  } 

  iterator erase(iterator itr )  
  {
    Node *p = itr.current;
    iterator retVal( p->next );
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p ;
    theSize--;

    return retVal;
  }
  iterator erase(iterator from, iterator to)
  {
    for( iterator itr = from; itr != to;)
      itr = erase( itr ) ;

    return to;
  }
  
  iterator find( Object & x)
  {
    int flag_find = 0;
    iterator itr = begin();
    int i=1;
    iterator itr_end = end();
    while(itr != itr_end){
      if( *itr == x ){
	std::cout << "您查找的元素在List中第" << i << "个位置\n" <<std::endl;
	return itr;
      }
      itr++;
      i++;
    }
    std::cout << "没有在List中发现您查询的元素\n" << std::endl;
    return begin() ;
  }
  /**<我按照作业要求额外加上的find函数*/
public:
  iterator itr = begin();

  
private:
  int theSize;
  Node *head;
  Node *tail;
  void init()
  {
    theSize = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    tail->prev = head;
  }

  
};
